#
# @lc app=leetcode.cn id=46 lang=python3
#
# [46] 全排列
#
# https://leetcode-cn.com/problems/permutations/description/
#
# algorithms
# Medium (78.47%)
# Likes:    1767
# Dislikes: 0
# Total Accepted:    509.2K
# Total Submissions: 648.8K
# Testcase Example:  '[1,2,3]'
#
# 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
# 
# 
# 
# 示例 1：
# 
# 
# 输入：nums = [1,2,3]
# 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
# 
# 
# 示例 2：
# 
# 
# 输入：nums = [0,1]
# 输出：[[0,1],[1,0]]
# 
# 
# 示例 3：
# 
# 
# 输入：nums = [1]
# 输出：[[1]]
# 
# 
# 
# 
# 提示：
# 
# 
# 1 <= nums.length <= 6
# -10 <= nums[i] <= 10
# nums 中的所有整数 互不相同
# 
# 
#

# @lc code=start
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # f(n) input nums and output results
        # f(n - 1) ,确定output之间的关系
        # 所以，必然有for，results这个操作。
        # 添加终止条件。
        # 本题而言，终止条件只跟input parameters有关系。
        if len(nums) == 1:
            return [nums]
        if nums is None:
            return []
        # for f(n)
        results = []
        for i in nums:
            # for j in f(n - 1)'s result
            for j in self.permute([k for k in nums if k != i]):
                # i 是单一元素，j是result中的一个list。
                results.append([i] + j)
        return results

# @lc code=end

